↓Skip to main content
  1. Teaching/

[L3] Algorithmique Programmation et Complexité

Table of Contents

Organisation de l’UE #

Cette page regroupe les documents de cours, TD et TP pour le module Lifapc, semestre de printemps. Pour le semestre d’automne, référez vous à la page de Raphaëlle Chaîne.

Intervenants #

  • Vincent Nivoliers (Cours, TD A, TP A1)
  • Baptiste Genest (TD B)
  • Joachim Cendrier (TP A2)
  • Jean-Christophe Mignot (TP B1)
  • Jean-Claude Iehl (TP B1)

Cours #

Introduction #

Cours d’introduction, de présentation de la matière, des modalités de contrôle, et de présentation du projet.

Classes de complexité #

Cours introduisant la notion de classe de complexité et la notation O pour l’étude asymptotique des algorithmes.

Parcours de graphes #

Cours introduisant les algorithmes principaux de parcours de graphes : parcours en profondeur, en largeur, et recherche de plus courts chemins par l’algorithme de Dijkstra et la variante A*.

Master Theorem #

Cours introduisant le Master Theorem, outil essentiel pour l’analyse de la complexité des algorithmes récursifs.

Hashage #

Cours introduisant les tables de hashage.

Algorithmes de tri rapides #

Algorithmes de tri rapides : arbres binaires de recherche, skip-lists, tas, quicksort, tri fusion, tri par radical

TD #

Rappels sur la récurrence et la récursivité #

TD de rappels sur la récursivité et les preuves par récurrence. Un premier exercice sur une paire de suite imbriquées, un second classique sur la célèbre suite de Fibonacci, et un dernier classique également sur les tours de Hanoï.

Complexité des algorithmes itératifs #

Calcul du nombre d’opérations réalisées dans les boucles for, application à l’analyse de complexité de deux algorithmes naïfs de tri dans le meilleur cas, le pire cas, et en moyenne.

Notations de complexité et étude de meilleur et pire cas #

Notation de complexité grand 0, grand theta et grand oméga, manipulation de ces notations.

Introduction aux graphes et complexité des Skip Lists #

Recherche et insertion dans une skip list, intuition de la complexité moyenne, et introduction aux parcours de graphes via un problème d’échecs.

Algorithme de Dijkstra #

Application de l’algorithme de Dijkstra, étude des cas limite et de sa complexité.

Tas binaire #

Gestion d’un tas binaire, et extension à la définitino du tri par tas.

AVL #

Équilibrage des arbres binaires de recherche via la technique des AVL

Diviser pour régner, Master Theorem #

Étude d’algorithmes de type diviser pour régner avec le Master Theorem.

Hashage #

Stratégies de rehashage dans les tables de hashage et probabilité de collision.

Pivot, quicksort et quickselect #

Principe du pivot, algorithmes quicksort et quickselect.

TP #

Listes chaînées #

Rappels sur le C et le C++, les pointeurs, les références, l’allocation dynamique, les passages de paramètres, et la définition de structures. Mise en application à la programmation de listes chaînées (rappel).

Skip Lists #

Mise en place de skip lists : listes chaînées permettant d’implémenter le type set.

Union-Find #

Mise en place d’une structure d’Union-Find, et application à la création de labyrinthes

AVL #

Mise en place de l’équilibrage automatique des arbres binaires de recherche par la stratégie des AVL.

annales #

Vous trouverez ci-dessous une partie des anciennes interros et examens des années précédentes. Je ne fournirai pas de corrigé directement. Pour vous entraîner, faites l’interro et contactez moi (Vincent Nivoliers) pour discuter de ce que vous avez fait.

Interros de TD #

TP notés #

Examens #